package com.xxd.algo.newcode.base01.class05;

/**
 * @author: XiaoDong.Xie
 * @create: 2020-07-25 11:53
 * @description:
 */
public class Code11_IsFullTree {


    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static boolean isFull(Node head) {
        if (head == null) {
            return true;
        }
        Info data = processFull(head);
        return data.nodes == ((1 << data.height) - 1);
    }

    private static Info processFull(Node head) {
        if (head == null) {
            return new Info(0, 0);
        }
        Info leftData = processFull(head.left);
        Info rightData = processFull(head.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        int nodes = leftData.nodes + rightData.nodes + 1;
        return new Info(height, nodes);
    }

    /**
     * dp 信息
     */
    public static class Info {
        public int height;
        public int nodes;

        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        System.out.println(isFull(head));
    }
}
